package com.bascker.algorithm.practice.search.bfs;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.stream.Stream;

/**
 * 有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。
 * 每个拨轮可以自由旋转：例如把 '9' 变为  '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。锁的初始数字
 * 为 '0000' ，一个代表四个拨轮的数字的字符串。列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个
 * 元素相同，这个锁将会被永久锁定，无法再被旋转。字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无
 * 论如何不能解锁，返回 -1。
 * <p>
 * Note:
 * 1) 死亡列表 deadends 的长度范围为 [1, 500]
 * 2) 目标数字 target 不会在 deadends 之中
 * 3) 每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生
 * <p>
 * in:  deadends = ["0201","0101","0102","1212","2002"], target = "0202"
 * out: 6
 * 可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
 * <p>
 * <p>
 * 一定要理解“每次旋转都只能旋转一个拨轮的一位数字。” 这句话。这句话的意思，每次只能有一个位置，可以网上或往下波动一次。
 * 如 0000, 拨动一次可以有以下 8 种选择:
 * 往上拨一次：1000,   0100,   0010,   0001
 * 往下拨一次：9000,   0900,   0090,   0009
 * <p>
 * from: leetcode T705
 */
public class OpenLock {

    /**
     * 将 k 位置的拨轮往上拨一次
     */
    public String upOne(String s, int k) {
        char[] ch = s.toCharArray();
        char c = ch[k];
        if (c == '9') {
            ch[k] = '0';
        } else {
            ch[k] = (char) (c + 1);
        }

        return String.valueOf(ch);
    }

    /**
     * 将 k 位置的拨轮往下拨一次
     */
    public String downOne(String s, int k) {
        char[] ch = s.toCharArray();
        char c = ch[k];
        if (c == '0') {
            ch[k] = '9';
        } else {
            ch[k] = (char) (c - 1);
        }

        return String.valueOf(ch);
    }

    /**
     * 解法学习自 labuladong
     */
    public int openLock(String[] deadends, String target) {
        final Set<String> ds = new HashSet<>();
        Stream.of(deadends).forEach(s -> ds.add(s));

        final Queue<String> queue = new LinkedList<>();
        // 记录访问过的密码
        final Set<String> visited = new HashSet<>();

        // 从起点开始进行 BFS
        String org = "0000";
        queue.offer(org);
        int step = 0;

        // 只要元素入队，就当做其已被访问
        visited.add(org);

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String s = queue.poll();
                // 是否是死亡密码，若是则去掉该选择项
                if (ds.contains(s)) {
                    continue;
                }

                // 是否安全到达解锁
                if (target.equals(s)) {
                    return step;
                }

                // 将四个拨轮的上下拨动后的值，入队
                for (int j = 0; j < 4; j++) {
                    String up = upOne(s, j);
                    if (!visited.contains(up)) {
                        queue.offer(up);
                        visited.add(up);
                    }

                    String down = downOne(s, j);
                    if (!visited.contains(down)) {
                        queue.offer(down);
                        visited.add(down);
                    }
                }
            }

            // 当前层没有解锁，进入下一层，步数加一
            step++;
        }

        // 全部可能都没解开锁，说明不存在解锁路径，返回 -1
        return -1;
    }

}
